package com.learn.algorithm.tree;


import com.learn.algorithm.Sort;

import java.util.Arrays;

public class LeetCode421 {
    public static int findMaximumXOR(int[] nums) {
        build(nums);
        int ans = 0;
        for (int num : nums) {
            ans = Math.max(ans, maxXor(num));
        }
        clear();
        return ans;
    }

    public static int MAX = 3000001;
    public static int[][] tree = new int[MAX][2];
    public static int cnt;
    public static int high;

    public static void build(int[] nums) {
        cnt = 1;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        high = 31 - Integer.numberOfLeadingZeros(max);
        for (int num : nums) {
            insert(num);
        }
    }

    public static void insert(int num) {
        int cur = 1;
        for (int i = high, path; i >= 0; i--) {
            path = (num >> i) & 1;
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
    }

    public static int maxXor(int num) {
        int ans = 0;
        int cur = 1;
        for (int i = high, status, want; i >= 0; i--) {
            status = (num >> i) & 1;
            want = status ^ 1;
            if (tree[cur][want] == 0) {
                want ^= 1;
            }
            ans |= (status ^ want) << i;
            cur = tree[cur][want];
        }
        return ans;
    }

    public static void clear() {
        for (int i = 1; i <= cnt; i++) {
            tree[i][0] = tree[i][1] = 0;
        }
    }

    public static int findMaxXor(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                ans = Math.max(ans, nums[i] ^ nums[j]);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 2000; i++) {
            int N = 100;
            int[] test = new int[N];
            for (int j = 0; j < N; j++) {
                test[j] = (int) (Math.random() * 10);
            }
            if (findMaximumXOR(test) != findMaxXor(test)) {
                System.out.println(findMaxXor(test));
                System.out.println(findMaximumXOR(test));
                Sort.print(test);
                break;
            }
        }
    }
}
